一、DLCN [2013]

《Spectral Networks and Deep Locally Connected Networks on Graphs》

1. 卷积神经网络（ Convolutional Neural Networks: CNNs ）在机器学习问题中非常成功，其中底层数据representation 的坐标具有网格结构（grid structure）（一维、二维、或三维的网格），并且在这些坐标中，这些待研究的数据相对于该网格具有平移相等性（translational equivariance）或平移不变性 （translational invariance）。语音、图像、视频就是属于这一类问题的著名的例子。

   在常规网格上，CNN 能够利用多种结构来很好地协同工作，从而大大减少系统中的参数数量：

   • 平移结构 （translation structure）：它允许使用 filter 而不是通用的线性映射，从而实现权重共享（weight sharing）。

   • 空间局部性：filter 的尺寸通常都远远小于输入信号的尺寸。

   • 多尺度：通过步长大于一的卷积或者池化操作来减少参数，并获得更大的感受野（ receptive field） 。

   然而在许多情况下，数据并不是网格结构，如社交网络数据，因此无法在其上应用标准的卷积网络。图 （graph ）提供了一个自然框架来泛化网格结构，并扩展了卷积的概念。在论文《Spectral Networks and Deep Locally Connected Networks on Graphs》中，作者将讨论在除了常规网格之外的图上构建深度神经网络。论文提出了两种不同的结构：

   • 基于空域的卷积构建 （Spatial Construction ）：通过将空间局部性和多尺度扩展到通用的图结构，并使用它们来定义局部连接和池化层，从而直接在原始图结构上执行卷积。

   • 基于谱域的卷积构建（Spectral Construction）：对图结构进行傅里叶变换之后，在谱域进行卷积。

   论文主要贡献如下：

   • 论文表明，从给定的图结构输入，可以获得参数为 $O(n)$$O(n)$ 的有效架构（$n$$n$ 为输入节点总数），并且论文在低维的图数据集上进行了验证。

   • 论文介绍了一种使用 $O(1)$$O(1)$ 参数的结构，通过实验验证了该结构并讨论了它与图上的谐波分析问题（harmonic analysis problem） 的联系。

1.1 基础概念（读者补充）

1.1.1 拉普拉斯算子

1. 散度定义：给定向量场 $\overrightarrow{\mathbf{F}}(\overrightarrow{\mathbf{x}})$$\mathbf{\vec F}(\mathbf{\vec x})$，设 $\mathrm{\Sigma }$$\Sigma$ 为围绕某一点 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的一个封闭曲面，$dS$$dS$ 为曲面上的微元，$\overrightarrow{\mathbf{n}}$$\mathbf{\vec n}$ 为该微元的法向量，则该曲面的通量为：

   $${\mathbf{\Phi }}_{\overrightarrow{\mathbf{F}}}(\mathrm{\Sigma })={\oint }_{\mathrm{\Sigma }}\overrightarrow{\mathbf{F}}\cdot \overrightarrow{\mathbf{n}}dS$$

   当 $\mathrm{\Sigma }$$\Sigma$ 趋近于零时，即可得到 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 点的散度：

   $$\text{div}\overrightarrow{\mathbf{F}}(\overrightarrow{\mathbf{x}})=\mathrm{\nabla }\cdot \overrightarrow{\mathbf{F}}=\mathrm{\nabla }\cdot \overrightarrow{\mathbf{F}}=\sum _{i=1}^n\frac{\partial F_i}{\partial x_i}$$

   其中 $\overrightarrow{\mathbf{x}}=(x_1,\cdots ,x_n{)}^{\mathrm{\top }},\overrightarrow{\mathbf{F}}=(F_1,\cdots ,F_n{)}^{\mathrm{\top }}$$\mathbf{\vec x} = (x_1,\cdots,x_n)^\top, \mathbf{\vec F} = (F_1,\cdots,F_n)^\top$ 。

   散度的物理意义为：在向量场中从周围汇聚到该点或者从该点流出的流量。

2. 旋度定义：给定向量场 $\overrightarrow{\mathbf{F}}(\overrightarrow{\mathbf{x}})$$\mathbf{\vec F}(\mathbf{\vec x})$，设 $\mathrm{\Gamma }$$\Gamma$ 为围绕某一点 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 的一个封闭曲线，$dl$$dl$ 为曲线上的微元，$\overrightarrow{\tau }$${\vec \tau }$ 为该微元的切向量，则该曲线的环量为：

   $${\mathbf{\Theta }}_{\overrightarrow{\mathbf{F}}}(\mathrm{\Gamma })={\oint }_{\mathrm{\Gamma }}\overrightarrow{\mathbf{F}}\cdot \overrightarrow{\tau }dl$$

   当 $\mathrm{\Gamma }$$\Gamma$ 趋近于零时，即可得到 $\overrightarrow{\mathbf{x}}$$\mathbf{\vec x}$ 点的旋度：

   $$\text{curl}\overrightarrow{\mathbf{F}}(\overrightarrow{\mathbf{x}})=\mathrm{\nabla }\times \overrightarrow{\mathbf{F}}$$

   在三维空间中，上式等于：

   $$\begin{array}{c}\mathrm{\nabla }\times \overrightarrow{\mathbf{F}}=\left|\begin{array}{ccc}\overrightarrow{\mathbf{i}}& \overrightarrow{\mathbf{j}}& \overrightarrow{\mathbf{k}}\\ \frac{\partial }{\partial x}& \frac{\partial }{\partial y}& \frac{\partial }{\partial z}\\ F_x& F_y& F_z\end{array}\right|\\ =(\frac{\partial F_z}{\partial y}-\frac{\partial F_y}{\partial z})\overrightarrow{\mathbf{i}}+(\frac{\partial F_x}{\partial z}-\frac{\partial F_z}{\partial x})\overrightarrow{\mathbf{j}}+(\frac{\partial F_y}{\partial x}-\frac{\partial F_x}{\partial y})\overrightarrow{\mathbf{k}}\end{array}$$

   旋度的物理意义为：向量场对于某点附近的微元造成的旋转程度，其中:

   • 旋转的方向表示旋转轴，它与旋转方向满足右手定则。

   • 旋转的大小是环量与环面积之比。

3. 拉普拉斯算子定义：给定函数 $f(\overrightarrow{\mathbf{x}})$$f(\mathbf{\vec x})$ ，其中 $\overrightarrow{\mathbf{x}}=(x_1,\cdots ,x_n{)}^{\mathrm{\top }}$$\mathbf{\vec x} = (x_1,\cdots,x_n)^\top$ ，则梯度定义为：

   $$\mathrm{\nabla }f={(\frac{\partial f}{\partial x_1},\cdots \frac{\partial f}{\partial x_n})}^{\mathrm{\top }}$$

   梯度的物理意义为：函数值增长最快的方向。

   梯度的散度为拉普拉斯算子，记作：

   $${\mathrm{\nabla }}^{2}f=\mathrm{\nabla }\cdot \mathrm{\nabla }f=\sum _{i=1}^n\frac{{\partial }^{2}f}{\partial x_i^2}$$

   • 由于所有的梯度都朝着 $f$$f$ 极大值点汇聚、从 $f$$f$ 极小值点流出，因此拉普拉斯算子衡量了空间中每一点，该函数的梯度是倾向于流出还是流入。

   • 拉普拉斯算子也能够衡量函数的平滑度smoothness：函数值没有变化或者线性变化时，二阶导数为零；当函数值突变时，二阶导数非零。

4. 图拉普拉斯矩阵：假设 $f(x)$$f(x)$ 为离散的一维函数，则一阶导数为一阶差分：

   $$f^{\prime }(x)=\frac{\partial f(x)}{\partial x}\simeq f(x+1)-f(x)$$

   二阶导数为二阶差分：

   $$\begin{array}{c}{\mathrm{\nabla }}^{2}f=f^{\prime \prime }(x)=\frac{{\partial }^{2}f(x)}{\partial x^2}=f^{\prime }(x)-f^{\prime }(x-1)=[f(x+1)-f(x)]-[f(x)-f(x-1)]\\ =f(x+1)+f(x-1)-2f(x)\end{array}$$

   一维函数其自由度可以理解为2，分别是 +1 和 -1 两个方向。因此二阶导数等于函数在所有自由度上微扰之后获得的增益。

   推广到图结构 $G=(V,E)$$G=(V,E)$，其中节点数量为 $|V|$$|V|$ 。假设邻接矩阵为 $\mathbf{W}$$\mathbf W$ ，并且任意两个节点之间存在边（即使不存在边则我们也可以假设存在一个 $w_{i,j}=0$$w_{i,j} = 0$ 的”虚拟“边 ）。对于其中任意节点 $i$$i$ ，对其施加微扰之后该节点可以到达其它任意节点，因此图的自由度为 $|V|$$|V|$ 。

   令 $f_i$$f_i$ 为函数 $f(\cdot )$$f(\cdot)$ 在节点 $i$$i$ 的值，定义 $\overrightarrow{\mathbf{f}}=(f_1,f_2,\cdots ,f_{|V|}{)}^{\mathrm{\top }}\in {\mathbb{R}}^{|V|}$$\mathbf{\vec f} = (f_1,f_2,\cdots,f_{|V|})^\top\in \mathbb R^{|V|}$ ，它表示函数 $f$$f$ 在图 $G=(V,E)$$G=(V,E)$ 上的取值。对于节点 $i$$i$ ，其扰动到节点 $j$$j$ 的增益时 $(f_j-f_i)$$(f_j-f_i)$ ，不过这里通常写成负的形式，即 $(f_i-f_j)$$(f_i-f_j)$ 。考虑到边的权重，则增益为：$w_{i,j}(f_i-f_j)$$w_{i,j}(f_i-f_j)$ 。

   函数 $f(\cdot )$$f(\cdot)$ 也可以视为定义在图上的信号 signal 。

   对于节点 $i$$i$ ，总的增益为拉普拉斯算子在节点 $i$$i$ 的值。即：

   $$\begin{array}{c}({\mathrm{\nabla }}^{2}f{)}_i=\sum _j\frac{{\partial }^2{f}_i}{\partial j^2}\simeq \sum _j{w}_{i,j}(f_i-f_j)=\left(\sum _j{w}_{i,j}\right)f_i-\sum _j{w}_{i,j}{f}_j\\ ={\left(\mathbf{D}\overrightarrow{\mathbf{f}}\right)}_i-{\left(\mathbf{W}\overrightarrow{\mathbf{f}}\right)}_i={((\mathbf{D}-\mathbf{W})\overrightarrow{\mathbf{f}})}_i\end{array}$$

   其中： $\mathbf{D}$$\mathbf D$ 为图的度矩阵degree matrix ，$(\cdot {)}_i$$(\cdot)_i$ 表示该向量的第 $i$$i$ 个元素。

   考虑所有的节点，则有：

   $${\mathrm{\nabla }}^2\overrightarrow{\mathbf{f}}=(\mathbf{D}-\mathbf{W})\overrightarrow{\mathbf{f}}$$

   定义拉普拉斯矩阵 $\mathbf{L}=\mathbf{D}-\mathbf{W}$$\mathbf L = \mathbf D - \mathbf W$ ，因此在图的拉普拉斯算子就是拉普拉斯矩阵。

   上述结果都是基于 $f_i$$f_i$ 为标量推导，实际上当 $f_i$$f_i$ 为向量时也成立。

5. 假设图的节点数量为 $m$$m$，图的拉普拉斯矩阵 $\mathbf{L}\in {\mathbb{R}}^{m\times m}$$\mathbf L\in \mathbb R^{m\times m}$ 是一个半正定对称矩阵，它具有以下性质：

   • 对称矩阵一定有 $m$$m$ 个线性无关的特征向量。

   • 半正定矩阵的特征值一定是非负的。

   • 对称矩阵的特征向量相互正交，即：所有特征向量构成的矩阵为正交矩阵。

   因此有拉普拉斯矩阵的谱分解：

   $$\mathbf{L}{\overrightarrow{\mathbf{u}}}_k={\lambda }_k{\overrightarrow{\mathbf{u}}}_k$$

   其中 ${\overrightarrow{\mathbf{u}}}_k$$\mathbf{\vec u}_k$ 为第 $k$$k$ 个特征向量，${\lambda }_k$$\lambda_k$ 为第 $k$$k$ 个特征值。

   解得：$\mathbf{L}=\mathbf{U}\mathbf{\Lambda }{\mathbf{U}}^{\mathrm{\top }}$$\mathbf L = \mathbf U \mathbf\Lambda \mathbf U^\top$ ，其中 ：

   $$\begin{array}{c}\mathbf{U}=[{\overrightarrow{\mathbf{u}}}_1,{\overrightarrow{\mathbf{u}}}_2,\cdots ,{\overrightarrow{\mathbf{u}}}_m]\in {\mathbb{R}}^{m\times m}\\ \mathbf{\Lambda }=\left[\begin{array}{cccc}{\lambda }_1& 0& \cdots & 0\\ 0& {\lambda }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_m\end{array}\right]\end{array}$$

   $\mathbf{U}$$\mathbf U$ 每一列为特征向量构成的正交矩阵，$\mathbf{\Lambda }$$\mathbf\Lambda$ 为对应特征值构成的对角矩阵。

6. 根据 $\mathbf{L}=(\mathbf{D}-\mathbf{W})$$\mathbf L=(\mathbf D-\mathbf W)$ 的定义有：

   $$\begin{array}{c}\mathbf{L}\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right]=\overrightarrow{\mathbf{0}}\end{array}$$

   根据特征方程：$\mathbf{L}\overrightarrow{\mathbf{u}}=\lambda \overrightarrow{\mathbf{u}}$$\mathbf L\mathbf{\vec u} = \lambda \mathbf{\vec u}$ ，因此 $\lambda =0$$\lambda = 0$ 是 $\mathbf{L}$$\mathbf L$ 的一个特征值。由于半正定矩阵的特征值一定是非负的，因此 $\lambda =0$$\lambda =0$ 是 $\mathbf{L}$$\mathbf L$ 的最小特征值。

   在 $\mathbf{L}$$\mathbf L$ 对应的 $m$$m$ 维谱空间中，特征值 ${\lambda }_k$$\lambda_k$ 越小则表明拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ 在 ${\lambda }_k$$\lambda_k$ 对应的基 ${\overrightarrow{\mathbf{u}}}_k$$\mathbf{\vec u}_k$ 上的分量的信息越少，这意味着该分量是可以忽略的低频部分。其实图像压缩就是这个原理，把像素矩阵分解后，把小的特征值（低频部分）全部变成零。PCA 降维也是同样原理，把协方差矩阵特征分解后，取 top K 个特征值对应的特征向量作为新的特征空间。 如下图所示为包含 25 个节点的图，其 $\mathbf{L}$$\mathbf L$ 对应的 25 维空间中，最大特征值、第12 大特征值、次小特征值（因为最小特征值为零，因此第24 大特征值就是次小的）对应特征向量 ${\overrightarrow{\mathbf{u}}}_k$$\mathbf{\vec u}_k$ 的可视化。可以看到：特征值越大则对应特征向量的变化越剧烈，特征值越小则对应特征向量的变化越平缓。注意：最小特征值为零，并且对应的特征向量为全1 的向量（或者乘以常数倍），这意味着该特征向量在所有节点上取值相等（所以变化为零），即频率为零的分量。

1.1.2 卷积

1. 给定函数 $f(x)$$f(x)$， 其傅里叶变换为：

   $$f(x)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}F(k)e^{ikx}dk$$

   其中 $F(k)=\frac{1}{2\pi }{\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(x)e^{-ikx}dx$$F(k) = \frac{1}{2\pi}\int_{-\infty}^{\infty} f(x) e^{-ikx} dx$ 为傅里叶系数，即频率为 $k$$k$ 的振幅， $e^{-iwx}$$e^{-iwx}$ 为傅里叶基 fouries basis 。

   可以证明：$e^{-ikx}$$e^{-ikx}$ 为拉普拉斯算子的特征函数。证明：

   $${\mathrm{\nabla }}^2{e}^{{}_{-}ikx}=\frac{{\partial }^2{e}^{-ikx}}{\partial x^2}=-k^2{e}^{-ikx}$$

2. 如果将傅里叶变换推广到图上，则有类比：

   • 拉普拉斯算子对应于拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ 。

   • 频率 $k$$k$ 对应于拉普拉斯矩阵的特征值 ${\lambda }_k$$\lambda_k$ 。

   • 傅里叶基 $e^{-ikx}$$e^{-ikx}$ 对应于特征向量 ${\overrightarrow{\mathbf{u}}}_k$$\mathbf{\vec u}_k$ 。

   • 傅里叶系数 $F(k)$$F(k)$ 对应于 $F({\lambda }_k)$$F(\lambda_k)$ ，其中：

     $$\begin{array}{c}F({\lambda }_k)={\hat{f}}_k=\overrightarrow{\mathbf{f}}\cdot {\overrightarrow{\mathbf{u}}}_k\end{array}$$

     写成矩阵形式为：

     $$\widehat{\overrightarrow{\mathbf{f}}}={\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{f}}$$

     其中：

     • $\overrightarrow{\mathbf{f}}\in {\mathbb{R}}^m$$\mathbf{\vec f} \in \mathbb R^{m}$ 为图上定义的一个 $m$$m$ 维的信号（空域信号），它由每个节点的特征 $f_i$$f_i$ 组成。

     • $\widehat{\overrightarrow{\mathbf{f}}}$$\hat{\mathbf{\vec f}}$ 为图的傅里叶变换（谱域信号），它是在谱域上对应于不同特征值的振幅构成的向量。

       $\widehat{\overrightarrow{\mathbf{f}}}$$\hat{\mathbf{\vec f}}$ 其实就是 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$ 在由 $m$$m$ 个基向量 $\{{\overrightarrow{\mathbf{u}}}_1,\cdots ,{\overrightarrow{\mathbf{u}}}_m\}$$\left\{\mathbf{\vec u}_1,\cdots,\mathbf{\vec u}_m\right\}$ 所张成的谱空间中的坐标，${\hat{f}}_i$$\hat f_i$ 就是 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$ 在基向量 ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 上的投影。

   • 传统的傅里叶逆变换 ${\mathcal{F}}^{-1}(F(k))=f(x)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}F(k)e^{ikx}dk$$\mathcal F^{-1}(F(k)) = f(x) = \int_{-\infty}^\infty F(k)e^{ikx} dk$ 对应于图结构：

     $$f_i=\sum _{k=1}^m{\hat{f}}_k{u}_{k,i}$$

     其中 $u_{k,i}$$u_{k,i}$ 对应于特征向量 ${\overrightarrow{\mathbf{u}}}_k$$\mathbf{\vec u}_k$ 的第 $i$$i$ 个分量。写成矩阵的形式为：

     $$\overrightarrow{\mathbf{f}}=\mathbf{U}\widehat{\overrightarrow{\mathbf{f}}}$$

3. 卷积定理：两个函数在时域的卷积等价于在频域的相乘。

   $$\begin{array}{c}f(x)\ast h(x)={\mathcal{F}}^{-1}(F(k)\times H(k))={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}F(k)\times H(k)e^{ikx}dk\\ F(k)=\frac{1}{2\pi }{\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(x)e^{-ikx}dx\\ H(k)=\frac{1}{2\pi }{\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}h(x)e^{-ikx}dx\end{array}$$

   对应于图上有：

   $$\overrightarrow{\mathbf{f}}\ast \overrightarrow{\mathbf{h}}={\mathcal{F}}^{-1}(\widehat{\overrightarrow{\mathbf{f}}}\odot \widehat{\overrightarrow{\mathbf{h}}})=\mathbf{U}\left(\mathbf{K}\left({\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{f}}\right)\right)=\mathbf{U}\mathbf{K}{\mathbf{U}}^{\mathrm{\top }}\overrightarrow{\mathbf{f}}$$

   其中： $\odot$$\odot$ 为逐元素乘积，$\mathbf{U}$$\mathbf U$ 为拉普拉斯矩阵 $\mathbf{L}$$\mathbf L$ 特征向量组成的矩阵（每一列为一个特征向量），$\mathbf{K}$$\mathbf K$ 为对角矩阵：

   $$\begin{array}{c}\mathbf{K}=\left[\begin{array}{cccc}\overrightarrow{\mathbf{h}}\cdot {\overrightarrow{\mathbf{u}}}_1& 0& \cdots & 0\\ 0& \overrightarrow{\mathbf{h}}\cdot {\overrightarrow{\mathbf{u}}}_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & \overrightarrow{\mathbf{h}}\cdot {\overrightarrow{\mathbf{u}}}_m\end{array}\right]\end{array}$$

   这里将逐元素乘积转换为矩阵乘法。

4. 图卷积神经网络的核心就是设计卷积核，从上式可知卷积核就是 $\mathbf{K}$$\mathbf K$ 。我们可以直接令 $\overrightarrow{\mathbf{h}}\cdot {\overrightarrow{\mathbf{u}}}_k={\theta }_k$$\mathbf{\vec h}\cdot \mathbf{\vec u}_k = \theta_k$ ，然后学习卷积核：

   $$\begin{array}{c}\mathbf{K}=\left[\begin{array}{cccc}{\theta }_1& 0& \cdots & 0\\ 0& {\theta }_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\theta }_m\end{array}\right]\end{array}$$

   我们并不关心 $\overrightarrow{\mathbf{h}}$$\mathbf{\vec h}$，仅仅关心傅里叶变换之后的 $\widehat{\overrightarrow{\mathbf{h}}}$$\hat{\mathbf{\vec h}}$ 。

1.2 空域构建 Spatial Construction

1.2.1 基本概念

1. 在通用的图结构上针对 CNN 最直接的推广是考虑多尺度的、局部的感受野。为此，我们使用一个加权图 $G=(\mathbf{\Omega },\mathbf{W})$$G = (\mathbf\Omega, \mathbf W)$ 来代替网格结构，其中 $\mathbf{\Omega }$$\mathbf\Omega$ 为大小为 $m$$m$ 的节点集合，$\mathbf{W}\in {\mathbb{R}}^{m\times m}$$\mathbf W\in \mathbb R^{m\times m}$ 为对称、非负的权重矩阵（这里采用无向图）。

   这里的权重指的是图中边的权重，而不是神经网络的权重。

2. 基于 $\mathbf{W}$$\mathbf W$ 的局部性（ locality）：可以很容易地在图结构中推广局部性的概念。实际上，图中的权重决定了局部性的概念。例如，在 $\mathbf{W}$$\mathbf W$ 上定义邻域的一种直接方法是设置阈值 $\delta >0$$\delta\gt 0$，并设置邻域为：

   $${\mathcal{N}}_{\delta }(j)=\{i\mid i\in \mathbf{\Omega },W_{i,j}>\delta \}$$

   其中 ${\mathcal{N}}_{\delta }(j)$$\mathcal N_\delta(j)$ 为节点 $j$$j$ 的邻域节点集合。

   在执行卷积时，我们可以仅仅考虑将感受野限制在这些邻域上的 sparse filter ，从而获得局部连接的网络（locally connected network），从而将卷积层的参数数量减少到 $O(S\times m)$$O(S\times m)$ （而不是 $O(m^2)$$O(m^2)$），其中 $S$$S$ 为平均邻域大小。

   每个节点需要 $S$$S$ 个参数，一共 $m$$m$ 个节点，所以参数数量是 $O(S\times m)$$O(S\times m)$

3. 图的多分辨率（multiresolution）分析：CNN 通过池化（pooling） 层和降采样（subsampling）层来减少feature map 的尺寸，在图结构上我们同样可以使用多尺度聚类（multiscale clustering）的方式来获得多尺度结构。在图结构上如何进行多尺度聚类仍然是个开发的研究领域，我们这里根据节点的邻域进行简单的聚类。

   图的邻域结构天然地代表了某种意义上的聚类。比如，社交网络的一阶邻域代表用户的直接好友圈子，以一阶邻域来聚类则代表了一个个的”小团体“。基于这些 ”小团体“ 进行聚类得到的高阶聚类可能包含了国家的信息，比如”中国人“被聚合在一个高阶聚类中，”美国人“被聚合在另一个高阶聚类中。

   下图给出了多尺度层次聚类的示意图（两层聚类)。原始的12个节点为灰色。第一层有6 个聚类，聚类中心为彩色节点，聚类以彩色块给出。第二层有3 个聚类，聚类以彩色椭圆给出。

   

1.2.2 深度局部连接网络 Deep Locally Connected Networks

1. 空域构建（spatial construction）从图的多尺度聚类开始，并且我们考虑 $K$$K$ 个尺度（scale）。定义第 0 个尺度表示原始图，即 ${\mathbf{\Omega }}_0=\mathbf{\Omega }$$\mathbf\Omega_0 = \mathbf\Omega$ 。对于之后每个尺度的feature map， ${\mathbf{\Omega }}_k$$\mathbf\Omega_k$ 是通过聚类算法将feature map ${\mathbf{\Omega }}_{k-1}$$\mathbf\Omega_{k-1}$ 划分到 $d_k$$d_k$ 个聚类而得到，其中 $d_0$$d_0$ 为原始图的节点数量 $m$$m$ ，$k=1,2,\cdots ,K$$k=1,2,\cdots,K$ 。

   ${\mathbf{\Omega }}_k$$\mathbf\Omega_k$ 包含 $d_k$$d_k$ 个节点，这些节点是 $d_k$$d_k$ 个聚类的聚类中心。

   ${\mathbf{\Omega }}_{k-1}$$\mathbf\Omega_{k-1}$ 包含 $d_{k-1}$$d_{k-1}$ 个节点，第 $i$$i$ 个节点的邻域记做 ${\mathcal{N}}_{k,i}$$\mathcal N_{k,i}$。定义 ${\mathbf{\Omega }}_{k-1}$$\mathbf\Omega_{k-1}$ 中全部邻域集合的集合为：

   $${\mathcal{N}}_k=\{{\mathcal{N}}_{k,1},\cdots ,{\mathcal{N}}_{k,d_{k-1}}\}$$

   有了这些之后我们现在可以定义神经网络的第 $k$$k$ 层。不失一般性，我们假设输入信号是定义在 ${\mathbf{\Omega }}_0$$\mathbf\Omega_0$ 上的实值信号 （real signal）（即标量值） ，我们设第 $k$$k$ 层创建的 filter 数量为 $f_k$$f_k$（即输出通道数）。则第 $k$$k$ 层神经网络将 $f_{k-1}$$f_{k-1}$ 个 $d_{k-1}$$d_{k-1}$ 维的信号转换为 $f_k$$f_k$ 个 $d_k$$d_k$ 维的信号。

2. 正式地，假设第 $k$$k$ 层神经网络的输入为：

   $$\begin{array}{c}{\mathbf{X}}^{(k)}=\left[\begin{array}{cccc}{x}_{1,1}^{(k)}& x_{1,2}^{(k)}& \cdots & x_{1,f_{k-1}}^{(k)}\\ x_{2,1}^{(k)}& x_{2,2}^{(k)}& \cdots & x_{2,f_{k-1}}^{(k)}\\ ⋮& ⋮& \ddots & ⋮\\ x_{d_{k-1},1}^{(k)}& x_{d_{k-1},2}^{(k)}& \cdots & x_{d_{k-1},f_{k-1}}^{(k)}\end{array}\right]\in {\mathbb{R}}^{d_{k-1}\times f_{k-1}}\end{array}$$

   其中：

   • ${\mathbf{X}}^{(k)}$$\mathbf X^{(k)}$ 为第 $k$$k$ 层神经网络的输入 feature map 。

   • ${\mathbf{X}}^{(k)}$$\mathbf X ^{(k)}$ 的第 $i$$i$ 行定义为 ${\overrightarrow{\mathbf{x}}}_{i,:}^{(k)}={(x_{i,1}^{(k)},\cdots ,x_{i,f_{k-1}}^{(k)})}^{\mathrm{\top }}\in {\mathbb{R}}^{f_{k-1}}$$\mathbf {\vec x}^{(k)}_{i,:} = \left(x^{(k)}_{i,1},\cdots ,x^{(k)}_{i,f_{k-1}}\right)^\top\in \mathbb R^{f_{k-1}}$ 为 ${\mathbf{\Omega }}_{k-1}$$\mathbf\Omega_{k-1}$ 的第 $j$$j$ 个节点的 feature 。

   • ${\mathbf{X}}^{(k)}$$\mathbf X^{(k)}$ 的第 $j$$j$ 列定义为 ${\overrightarrow{\mathbf{x}}}_{:,j}^{(k)}={(x_{1,j}^{(k)},\cdots ,x_{d_{k-1},j}^{(k)})}^{\mathrm{\top }}\in {\mathbb{R}}^{d_{k-1}}$$\mathbf{\vec x}_{:,j}^{(k)} = \left(x_{1,j}^{(k)},\cdots,x_{d_{k-1},j}^{(k)}\right)^\top\in \mathbb R^{d_{k-1}}$ 为第 $j$$j$ 个信号（一共 $f_{k-1}$$f_{k-1}$ 个）。

   则第 $k$$k$ 层神经网络的第 $j$$j$ 个输出信号定义为：

   $${\overrightarrow{\mathbf{x}}}_{:,j}^{(k+1)}={\mathbf{L}}^{(k)}h\left(\sum _{j^{\prime }=1}^{f_{k-1}}{\mathbf{F}}_{j^{\prime },j}^{(k)}{\overrightarrow{\mathbf{x}}}_{:,j^{\prime }}^{(k)}\right),j=1,2,\cdots ,f_k$$

   其中：

   • 信号的每一维度表示一个通道，因此$f_{k-1}$$f_{k-1}$ 为输入通道数，$f_k$$f_k$ 为输出通道数。

   • ${\mathbf{F}}_{j^{\prime },j}^{(k)}{\overrightarrow{\mathbf{x}}}_{:,j^{\prime }}^{(k)}$$\mathbf F^{(k)}_{j^\prime,j} \mathbf{\vec x}_{:,j^\prime}^{(k)}$ 对第 $j^{\prime }$$j^\prime$ 个输入通道进行线性变换，变换矩阵为 ${\mathbf{F}}_{j^{\prime },j}^{(k)}$$\mathbf F^{(k)}_{j^\prime,j}$ 。

     $\sum _{j^{\prime }=1}^{f_{k-1}}{\mathbf{F}}_{j^{\prime },j}^{(k)}{\overrightarrow{\mathbf{x}}}_{:,j^{\prime }}^{(k)}$$\sum_{j^\prime=1}^{f_{k-1}} \mathbf F^{(k)}_{j^\prime,j} \mathbf{\vec x}_{:,j^\prime}^{(k)}$ 的物理意义为：第 $j$$j$ 个输出通道由所有输入通道的线性变换进行 sum 聚合而来。

   • ${\mathbf{F}}_{j^{\prime },j}^{(k)}\in {\mathbb{R}}^{d_{k-1}\times d_{k-1}}$$\mathbf F^{(k)}_{j^\prime,j} \in \mathbb R^{d_{k-1}\times d_{k-1}}$ 为一个稀疏矩阵（作为 filter），它表示应用于第 $j^{\prime }$$j^\prime$ 个输入通道、第 $j$$j$ 个输出通道的参数矩阵。

     ${\mathbf{F}}_{j^{\prime },j}^{(k)}$$\mathbf F^{(k)}_{j^\prime,j}$ 的非零项由 ${\mathcal{N}}_k$$\mathcal N_k$ 来定义，即：

     $$\begin{array}{c}{F}_{j^{\prime },j}^{(k)}(u,v)=\{\begin{array}{ll}{\theta }_{j^{\prime },j}^{(k)}(u,v),& v\in {\mathcal{N}}_{k,u}\\ 0,& \text{else}\end{array}\end{array}$$

     即：当节点 $v$$v$ 不在节点 $u$$u$ 的邻域中时 $F_{j^{\prime },j}^{(k)}(u,v)$$F_{j^\prime,j}^{(k)}(u,v)$ 为零，由于对称性此时 $F_{j^{\prime },j}^{(k)}(v,u)$$F_{j^\prime,j}^{(k)}(v,u)$ 也为零。$\{{\theta }_{j^{\prime },j}^{(k)}(u,v)\}$$\left\{\theta_{j^\prime,j}^{(k)}(u,v)\right\}$ 为 filter 的待学习的参数。

     这意味着在线性投影时，节点 $u$$u$ 的输出仅依赖于其邻域节点 ${\mathcal{N}}_{k,u}$$\mathcal N_{k,u}$ ，即局部性。

   • $h(\cdot )$$h(\cdot)$ 为非线性激活函数。

   • ${\mathbf{L}}^{(k)}$$\mathbf L^{(k)}$ 为第 $k$$k$ 层的池化矩阵，矩阵的行表示聚类 cluster id，列表示节点id ，矩阵中的元素表示每个节点对应于聚类中心的权重：如果是均值池化则就是 1 除以聚类中的节点数，如果是最大池化则是每个聚类的最大值所在的节点。

     ${\mathbf{L}}^{(k)}$$\mathbf L^{(k)}$ 用于将 $f_k$$f_k$ 个 $d_{k-1}$$d_{k-1}$ 维的输出通道的信号池化为 $f_k$$f_k$ 个 $d_k$$d_k$ 维的信号。

     $$\begin{array}{c}{\mathbf{L}}^{(k)}=\begin{array}{ccccccc}& {\text{node}}_1& {\text{node}}_2& {\text{node}}_3& \cdots & {\text{node}}_{d_{k-1}-1}& {\text{node}}_{d_{k-1}}\\ {\text{cluster}}_1& 1& 0& 0& \cdots & 0& 0\\ {\text{cluster}}_2& 0& 1/2& 0& \cdots & 0& 1\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ {\text{cluster}}_{d_k}& 0& 1/2& 0& \cdots & 1& 0\end{array}\in {\mathbb{R}}^{d_k\times d_{k-1}}\end{array}$$

3. ${\mathbf{\Omega }}_k$$\mathbf\Omega_k$ 和 ${\mathcal{N}}_k$$\mathcal N_k$ 的构建过程：

   • 初始化：${\mathbf{W}}_0=\mathbf{W}$$\mathbf W_0 = \mathbf W$ 。

   • 根据对 ${\mathbf{W}}_k$$\mathbf W_k$ 的 $ϵ\text{-covering}$$\epsilon\text{-covering}$ 得到 ${\mathbf{\Omega }}_k$$\mathbf\Omega_k$ 。理论上也可以采取其它聚类算法。

   • 对于 ${\mathbf{\Omega }}_k$$\mathbf\Omega_k$ ，其簇中心 $i,j$$i,j$ 之间的连接权重为两个簇之间的所有连接的权重之和：

     $$A_k(i,j)=\sum _{s\in {\mathbf{\Omega }}_k(i)}\sum _{t\in {\mathbf{\Omega }}_k(j)}{W}_{k-1}(s,t)$$

     然后按行进行归一化：

     $${\mathbf{W}}_k=\text{row-normalize}({\mathbf{A}}_k)$$

   • 根据 ${\mathbf{W}}_k$$\mathbf W_k$ 以及邻域阈值 $\delta$$\delta$ 得到 ${\mathcal{N}}_k$$\mathcal N_k$ 。

   如下图所示 $K=2$$K=2$ 。

   • ${\mathbf{\Omega }}_0$$\mathbf\Omega_0$ 表示第零层，它有 12 个节点（灰色），信号为一个通道（标量）。

   • ${\mathbf{\Omega }}_1$$\mathbf\Omega_1$ 表示第一层，其输入为 ${\mathbf{\Omega }}_0$$\mathbf\Omega_0$，输出 6 个节点，输出信号四个通道（四个filter ）。

   • ${\mathbf{\Omega }}_2$$\mathbf\Omega_2$ 表示第二层，其输入为 ${\mathbf{\Omega }}_1$$\mathbf \Omega_1$ ，输出 3 个节点，输出信号六个通道（六个filter）。

   每一层卷积都降低了空间分辨率spatial resolution，但是增加了空间通道数。

   

4. 假设 $S_k$$S_k$ 为 ${\mathcal{N}}_k$$\mathcal N_k$ 中平均邻居数量，则第 $k$$k$ 层卷积的平均参数数量为：

   $$O(S_k\times d_k\times f_k\times f_{k-1})$$

   实际应用中我们可以使得 $S_k\times d_k\simeq \alpha d_{k-1}$$S_k\times d_k\simeq \alpha d_{k-1}$ ，$\alpha$$\alpha$ 为一个升采样系数，通常为 $\alpha \in (1,4)$$\alpha \in (1,4)$ 。

   为什么这么做？论文并未说明原因。

5. 空域构建的实现非常朴素，其优点是不需要对图结构有很高的规整性假设 （regularity assumption）。缺点是无法在节点之间实现权重共享。

1.3 谱域构建 Spectral Construction

1. 可以通过图拉普拉斯算子来探索图的全局结构，从而推广卷积算子。

2. 假设构建一个 $K$$K$ 层的卷积神经网络，在第 $k$$k$ 层将输入的 feature map ${\mathbf{X}}^{(k)}\in {\mathbb{R}}^{d_{k-1}\times f_{k-1}}$$\mathbf X^{(k)}\in \mathbb R^{d_{k-1} \times f_{k-1}}$ 映射到 ${\mathbf{X}}^{(k+1)}\in {\mathbb{R}}^{d_{k-1}\times f_k}$$\mathbf X^{(k+1)}\in \mathbb R^{d_{k-1} \times f_{k}}$ ，则第 $k$$k$ 层网络的第 $j$$j$ 个输出通道为：

   $${\overrightarrow{\mathbf{x}}}_{:,j}^{(k+1)}=h\left(\sum _{j^{\prime }=1}^{f_{k-1}}\mathbf{U}{\mathbf{K}}_{j^{\prime },j}^{(k)}{\mathbf{U}}^{\mathrm{\top }}{\overrightarrow{\mathbf{x}}}_{:,j^{\prime }}^{(k)}\right)$$

   其中：

   • ${\overrightarrow{\mathbf{x}}}_{:,j^{\prime }}^{(k)}$$\mathbf{\vec x}^{(k)}_{:,j^\prime}$ 表示第 $j^{\prime }$$j^\prime$ 个输入信号，即 ${\mathbf{X}}^{(k)}$$\mathbf X^{(k)}$ 的第 $j^{\prime }$$j^\prime$ 列。

   • $\mathbf{U}$$\mathbf U$ 为拉普拉斯矩阵特征向量组成的矩阵（每一列表示一个特征向量）。

     实际应用中，通常仅仅使用拉普拉斯矩阵的最大 $D$$D$ 个特征向量，截断阈值 $D$$D$ 取决于图的固有规整性 regularity 以及图的节点数量。此时上式中的 $\mathbf{U}$$\mathbf U$ 替换为 ${\mathbf{U}}_D\in {\mathbb{R}}^{d_{k-1}\times D}$$\mathbf U_D\in \mathbb R^{d_{k-1}\times D}$ 。这可以减少参数和计算量，同时去除高频噪声。

   • ${\mathbf{K}}_{j^{\prime },j}^{(k)}\in {\mathbb{R}}^{d_{k-1}\times d_{k-1}}$$\mathbf K^{(k)}_{j^\prime,j}\in \mathbb R^{d_{k-1}\times d_{k-1}}$ 为第 $k$$k$ 层的、针对第 $j^{\prime }$$j^\prime$ 个输入通道、第 $j$$j$ 个输出通道的谱域 filter 。一般而言我们选择 filter ${\mathbf{K}}_{j^{\prime },j}^{(k)}$$\mathbf K_{j^\prime,j}^{(k)}$ 为对角矩阵，因此第 $k$$k$ 层卷积层的参数数量为 $f_{k-1}\times f_k\times d_{k-1}$$f_{k-1}\times f_k\times d_{k-1}$ 。

     我们将在后文看到如何将图的全局规整性和局部规整性结合起来，从而产生具有 $O(1)$$O(1)$ 参数的层，即模型参数的数量不依赖于输入节点数 $d_{k-1}$$d_{k-1}$。

   • $h(\cdot )$$h(\cdot)$ 为非线性激活函数。

3. 谱域构建可能受到以下事实的影响：大多数图仅在频谱的 top （即高频部分）才具有有意义的特征向量。即使单个高频特征向量没有意义，一组高频特征向量也可能包含有意义的信息。

   然而，我们的构建方法可能无法访问这些有意义的信息，因为我们使用对角线形式的卷积核，在最高频率处它是对角线形式因此仅包含单个高频特征向量（而不是一组高频特征向量）。

4. 傅里叶变换是线性变换，如何引入非线性目前还没有很好的办法。

   具体而言，当在空域执行非线性变换时，如何对应地在谱域执行前向传播和反向传播，目前还没有很好的办法，因此我们必须进行昂贵的 $\mathbf{U}$$\mathbf U$ 和 ${\mathbf{U}}^{\mathrm{\top }}$$\mathbf U^\top$ 矩阵乘法。

5. 为了降低参数规模，一个简单朴素的方法是选择一个一维的排列（ arrangement）（这个排列的顺序是根据拉普拉斯特征值的排序得到）。此时第 $k$$k$ 层网络的每个 filter ${\mathbf{K}}_{j^{\prime },j}^{(k)}$$\mathbf K_{j^\prime,j}^{(k)}$ 的对角线可以参数化为：

   $$\text{diag}\left({\mathbf{K}}_{j^{\prime },j}^{(k)}\right)={\mathcal{K}}^{(k)}{\overrightarrow{\alpha }}_{j^{\prime },j}^{(k)}$$

   其中： ${\mathcal{K}}^{(k)}\in {\mathbb{R}}^{d_{k-1}\times q_k}$$\mathcal K^{(k)}\in \mathbb R^{d_{k-1}\times q_k}$ 为三次样条核函数，${\alpha }_{j^{\prime },j}^{(k)}\in {\mathbb{R}}^{q_k}$$\alpha^{(k)}_{j^\prime,j}\in \mathbb R^{q_k}$ 为 $q_k$$q_k$ 个样条参数。

   假设采样步长正比于节点数量，即步长 $\alpha \sim d_{k-1}$$\alpha \sim d_{k-1}$ ，则 $q_k\sim d_{k-1}\times \frac{1}{\alpha }=O(1)$$q_k\sim d_{k-1}\times \frac{1}{\alpha} = O(1)$ ， 则谱域卷积的参数数量降低为：$f_{k-1}\times f_k$$f_{k-1}\times f_k$ 。

1.4 实验

1. 我们对 MNIST 数据集进行实验，其中MNIST 有两个变种。所有实验均使用 ReLU 激活函数以及最大池化。模型的损失函数为交叉熵，固定学习率为0.1 ，动量为 0.9 。

1.4.1 降采样 MNIST

1. 我们将MNIST 原始的 28x28 的网格数据降采样到 400 个像素，这些像素仍然保留二维结构。由于采样的位置是随机的，因此采样后的图片无法使用标准的卷积操作。

   采样后的图片的示例，空洞表示随机移除的像素点。

   

   空域层次聚类的可视化，不同的颜色表示不同的簇，颜色种类表示簇的数量。图 a 表示 $k=1$$k=1$ ，图 b 表示 $k=3$$k=3$ 。可以看到：层次越高，簇的数量越少。

   

   谱域拉普拉斯特征向量的可视化（谱域特征向量每个元素就是对应于每个节点的取值）。图a 表示 ${\overrightarrow{\mathbf{v}}}_2$$\mathbf{\vec v}_2$（对应于较小的特征值），图b 表示 ${\overrightarrow{\mathbf{v}}}_{20}$$\mathbf{\vec v}_{20}$ （对应于较大的特征值）。可以看到：特征值越小的特征向量对应于低频部分（变化越缓慢，左图），特征值越大的部分对应于高频部分（变化越剧烈，右图）。

   

2. 不同模型在 MNIST 上分类的结果如下。基准模型为最近邻模型 kNN ，FCN 表示带有 N 个输出的全连接层，LRFN 表示带有 N 个输出的空域卷积层，MPN 表示带有 N 个输出的最大池化层，SPN 是带有 N 个输出的谱域卷积层。

   • 基准模型 kNN （第一行）的分类性能比完整的（没有采样的）MNIST 数据集的 2.8% 分类误差率稍差。

   • 两层全连接神经网络（第二行）可以将测试误差降低到 1.8% 。

   • 两层空域图卷积神经网络（第三行的下面部分）效果最好，这表明空域卷积层核池化层可以有效的将信息汇聚到最终分类器中。

   • 谱域卷积神经网络表现稍差（第四行），但是它的参数数量最少。

   • 采用谱域平滑约束（选择top 的 $200$$200$ 个频率）的谱域卷积神经网络的效果优于常规的谱域卷积神经网络。

   

3. 由于 MNIST 中的数字由笔画组成，因此具有局部性。空域卷积通过filter ${\mathbf{F}}_{j^{\prime },j}^{(k)}$$\mathbf F^{(k)}_{j^\prime,j}$的定义从而很明确的满足这一约束，而谱域卷积则没有强制空间局部性。在谱域 filter 上添加平滑约束可以改善分类结果，因为 filter 被强制具有更好的空间局部性。

   • 图 (a),(b) 表示同一块感受野在空域卷积的不同层次聚类中的结果。

   • 图 (c),(d) 表示谱域卷积的两个拉普拉斯特征向量，可以看到结果并没有空间局部性。

   • 图 (e),(f) 表示采用平滑约束的谱域卷积的两个拉普拉斯特征向量，可以看到结果有一定的空间局部性。

   

1.4.2 球面 MNIST

1. 我们将MNIST 图片映射到一个球面上，构建方式为：

   • 首先从单位球面上随机采样 4096 个点 $\mathbb{S}=\{s_1,\cdots ,s_{4096}\}$$\mathbb S =\{s_1,\cdots,s_{4096}\}$ 。

   • 然后考虑三维空间的一组正交基 $\mathbf{E}=({\overrightarrow{\mathbf{e}}}_1,{\overrightarrow{\mathbf{e}}}_2,{\overrightarrow{\mathbf{e}}}_3)$$\mathbf E = (\mathbf{\vec e}_1,\mathbf{\vec e}_2,\mathbf{\vec e}_3)$ ，其中 $||{\overrightarrow{\mathbf{e}}}_1||=1,||{\overrightarrow{\mathbf{e}}}_2||=2,||{\overrightarrow{\mathbf{e}}}_3||=3$$||\mathbf{\vec e}_1|| = 1,||\mathbf{\vec e}_2||=2,||\mathbf{\vec e}_3||=3$ ，以及一个随机方差算子 $\mathbf{\Sigma }=(\mathbf{E}+\mathbf{W}{)}^{\mathrm{\top }}(\mathbf{E}+\mathbf{W})$$\mathbf\Sigma = (\mathbf E + \mathbf W)^\top(\mathbf E + \mathbf W)$ ，其中$\mathbf{W}$$\mathbf W$ 是一个方差为 ${\sigma }^2<1$$\sigma^2\lt 1$ 的独立同部分的高斯分布的分布矩阵。

   • 对原始 MNIST 数据集的每张图片，我们采样一个随机方差 ${\mathrm{\Sigma }}_i$$\Sigma_i$ 并考虑其主成分分析PCA 的一组基 $\{{\overrightarrow{\mathbf{u}}}_1,{\overrightarrow{\mathbf{u}}}_2,{\overrightarrow{\mathbf{u}}}_3\}$$\{\mathbf{\vec u}_1,\mathbf{\vec u}_2,\mathbf{\vec u}_3 \}$ 。这组基定义了一个平面内的旋转。我们将图片按照这组基进行旋转并使用双三次插值将图片投影到 $\mathbb{S}$$\mathbb S$ 上。

   由于数字 6 和 9 对于旋转是等价的，所以我们从数据集中移除了所有的 9 。

   下面给出了两个球面 MNIST 示例：

   

   下面给出了谱域构建的图拉普拉斯矩阵的两个特征向量的可视化。图a 表示 ${\overrightarrow{\mathbf{v}}}_{20}$$\mathbf{\vec v}_{20}$，图b 表示 ${\overrightarrow{\mathbf{v}}}_{\mathbf{100}}$$\mathbf{\vec v_{100}}$ 。可以看到：特征值越小的特征向量对应于低频部分（左侧），特征值越大的部分对应于高频部分（右侧）。

   

2. 首先考虑“温和”的旋转：${\sigma }^2=0.2$$\sigma^2=0.2$ ，结果如下表所示。

   • 基准的 kNN 模型的准确率比上一个实验（随机采样 MNIST ）差得多。

   • 所有神经网络模型都比基准 KNN 有着显著改进。

   • 空域构建的卷积神经网络、谱域构建的卷积神经网络在比全连接神经网络的参数少得多的情况下，取得了相差无几的性能。

   

3. 不同卷积神经网络学到的卷积核（即 filter ）如下图所示。

   • 图 (a),(b) 表示同一块感受野在空域卷积的不同层次聚类中的结果。

   • 图 (c),(d) 表示谱域卷积的两个拉普拉斯特征向量，可以看到结果并没有空间局部性。

   • 图 (e),(f) 表示采用平滑约束的谱域卷积的两个拉普拉斯特征向量，可以看到结果有一定的空间局部性。

   

4. 最后我们考虑均匀旋转，此时 $\{{\overrightarrow{\mathbf{u}}}_1,{\overrightarrow{\mathbf{u}}}_2,{\overrightarrow{\mathbf{u}}}_3\}$$\{\mathbf{\vec u}_1,\mathbf{\vec u}_2,\mathbf{\vec u}_3 \}$ 代表 ${\mathbb{R}}^3$$\mathbb R^3$ 中的随机的一组基，此时所有的模型的效果都较差。这时需要模型有一个完全的旋转不变性，而不仅仅是平移不变性。